package Sort;

import java.util.Deque;
import java.util.LinkedList;

public class Sort {
    //插入排序
    /*
    * 空间复杂度：O（1）
    * 时间复杂度：O（n*2）
    * 稳定性：稳定
    *        如果一个稳定的排序算法，是可以实现不稳地排序
    *        但是一个不稳定的排序算法，不可以实现稳定的排序*/
    public static void insertSort(int[] array) {
        for (int i = 1; i < array.length; i++) {
            int tmp = array[i];
            int j = i-1;
            for (; j >= 0; j--) {
                if (array[j] >tmp) {
                    array[j+1] = array[j];
                }else {
                    array[j+1] = tmp;
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }
    //希尔排序
    /*
    * 时间复杂度：O（N*1.3）
    * 空间复杂度：O（1）*/
    public static void shellSort(int[] array) {
        int gap = array.length;
        while (gap > 1) {
            shell(array,gap);
            gap /= 2;
        }
        //整体最后进行插入排序（因为=1的时候不进入循环，但是还需要排序一次）
        shell(array,1);
    }
    //插入排序 -> gap
    public static void shell(int[] array,int gap) {
        for (int i = gap; i < array.length; i++) {
            int tmp = array[i];
            int j = i-gap;
            for (; j >= 0; j -= gap) {
                if (array[j] > tmp) {
                    array[j+gap] = array[j];
                }else {
                    break;
                }
            }
            array[j+gap] = tmp;
        }
    }

    //选择排序
    /*时间复杂度：O（N*2
      空间复杂度：O（1）
      稳定性： 不稳定
      */
    public static void selectSort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            int minIndex = i;
            for (int j = i+1; j < array.length; j++) {//通过这个for循环，遇到比0下标小的就更新minIndex的值
                if (array[j] < array[minIndex]) {
                    minIndex = j;
                }//for循环走完之后minIndex存放的就是最小的值，然后让最小值和0下标的值交换
            }
            swap(array,i,minIndex);
        }
    }
    //交换
    private static void swap(int[] array,int i,int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

    //快速排序
    /*
    * 时间复杂度： N*logN
    *            最好情况：N*logN
    *            最坏情况：N^2   有序、逆序、优化！！
    *空间复杂度：
    *            最好情况：logN   满二叉树、完全二叉树
    *            最坏情况：N   有可能栈溢出，递归需要开辟空间
    * 稳定性：不稳定
    * */
    public static void quickSort(int[] array) {
        quick(array,0,array.length-1);
    }
    private static void quick(int[] array,int start,int end) {
        //为什么取大于号：1 2 3 4 5 6
        if (start >= end) {//递归结束条件
            return;  //如果递归左边的时候没有左树了，就结束了
        }

        //使用这个优化   主要解决减少递归的次数
        //如果在多次递归之后只剩下少量的数据，这个时候就用插入排序，比如递归到只剩下14个数据了，因为它像一颗
        //二叉树一样，剩下14个数据之后就趋于有序了，然后用插入排序，就不用递归了
        if (end - start + 1 < 14) {
            //插入排序
            insertSort2(array,start,end);
            return;
        }
        //System.out.println("start:"+start+" end: "+end);
        //三数取中法：如果取到一个基准，然后递归的时候没有左树和右树，比如
        //传过来的是一个有序的数组，这个时候就只有右树没有左树，这个时候递归的次数就多
        //但是取三个数中间大的一个数，这个时候就会少一点
        int index = midThree(array,start,end);
        swap(array,start,index);
        int pivot = partition(array,start,end);//划分
        //递归左半部分和右半部分，就像树一样
        quick(array,start,pivot-1);
        quick(array,pivot+1,end);
    }
    public static void insertSort2(int[] array,int left,int right) {
        for (int i = left; i < right; i++) {
            int tmp = array[i];
            int j;
            for (j = i-1; j >= 0; j--) {
                if (array[j] > tmp) {
                    array[j+1] = array[j];
                }else {
                    array[j+1] = tmp;
                    break;
                }
            }
            array[j+1] = tmp;
        }
    }
    private static int midThree(int[] array,int left,int right) {
        int mid = (left + right) / 2;
        //6  8
        if (array[left] < array[right]) {
            if (array[mid] < array[left]) {
                return left;
            }else if (array[mid] > array[right]) {
                return right;
            }else {
                return mid;
            }
        }else {
            //array[left] > array[right] 8  6
            if (array[mid] < array[right]) {
                return right;
            }else if (array[mid] > array[left]) {
                return left;
            }else {
                return mid;
            }
        }
    }
    //挖坑法    测试数据：6 1 2 7 9 3 4 5  10  8
    /*当快速排序有选择题的时候，优先使用挖坑法，然后再用hoare法，最后用左右指针法*/
    private static int partition1(int[] array,int left,int right) {
        int tmp = array[left];
        //左边找>6的，右边找<6的，以6为基准
        while (left < right) {
            //左边作为key，为什么先走右边，不先走左边？？
            //因为先走的是左边的，后走右边的，最后相遇的时候一定是比6大的，
            // 这个时候相遇了，然后会把比基准值大的换到前边去
            while (left < right && array[right] >= tmp) {//不能不取“=”，如果有相同元素就进入死循环了
                right--;
            }
            array[left] = array[right];
            while (left < right && array[left] <= tmp) {
                left++;
            }
            array[right] = array[left];
        }
        array[left] = tmp;
        return left;
    }
    //Hoare法   以6为基准，L找比6小的，R找比6大的，找到之后进行交换
    private static int partition(int[] array,int left,int right) {
        int tmp = array[left];
        int i = left;
        while (left < right){//相遇之前
            while (left < right && array[right] >= tmp) {//<6的
                right--;
            }
            while (left < right && array[left] <= tmp) {//找>6的
                left++;
            }
            //找完交换
            swap(array,left,right);
        }
        //相遇了
        swap(array,left,i);
        return left;
    }
    //左右指针法  改动
    private static int partition3(int[] array,int left,int right) {
        int tmp = array[left];
        int i = left;
        while (left < right){//相遇之前
            while (left < right && array[right] > tmp) {//<6的
                right--;
            }
            while (left < right && array[right] < tmp) {//找>6的
                left++;
            }
            //找完交换
            swap(array,left,right);
        }
        //相遇了
        swap(array,left,i);
        return left;
    }
    /*
    * 非递归实现快速排序
    * */
    public static void quickSort2(int[] array) {
        Deque<Integer> stack = new LinkedList<>();
        //首先找一次基准，然后把剩下左边和右边需要递归的部左边和右边入栈
        //看一下如果栈不为空，那么就需要出栈两个元素，一个是右边，一个是左边
        //分后根据左边和右边继续找基准
        int left = 0;
        int right = array.length - 1;
        int pivot = partition(array,left,right);
        if (pivot > left+1) {
            stack.push(left);
            stack.push(pivot-1);
        }
        if (pivot < right-1) {
            stack.push(pivot+1);
            stack.push(right);
        }
        //先去找基准，然后根据基准划分的再去重复找基准
        //重复的过程中需要判断能不能再入栈元素
        // （此时可能基准的左边或右边只有一个元素，就不能再入栈了）
        while (!stack.isEmpty()) {
            right = stack.pop();
            left = stack.pop();
            pivot = partition(array,left,right);
            //需要判断现在能不能继续入栈数据
            if (pivot > left+1) {
                stack.push(left);
                stack.push(pivot-1);
            }
            if (pivot < right-1) {
                stack.push(pivot+1);
                stack.push(right);
            }
        }
    }
    /*时间复杂度：N*logN
      空间复杂度：N
      稳定性：稳定的排序
             插入排序     冒泡排序      归并排序
    * */
    //归并排序  思路：先分解，然后递归左边，递归右边，当只剩下一个元素的时候，递归结束
    //递归结束之后就去合并递归后的数组，再合并的过程中排序
    public static void mergrSort1(int[] array) {
        mergeSortFunc(array,0,array.length-1);
    }
    private static void mergeSortFunc(int[] array,int left,int right) {
        //递归结束的条件
        if (left >= right) {
            return;
        }
        int mid = (left+right) / 2;
        mergeSortFunc(array,left,mid);
        mergeSortFunc(array,mid+1,right);
        //递归结束之后要进行数组的合并
        merge(array,left,right,mid);
    }
    private static void merge(int[] array,int start,int end,int mid) {
        int s1 = start;//为了好理解，先定义出分解之后的数组中的收尾下标
        //int e1 = mid;
        int s2 = mid + 1;
        //int e2 = end;
        //然后要有一个新的数组来存放这个分解之后的数据
        int[] tmp = new int[end-start+1];
        int k = 0;
        //要保证两个分解之后的数组都有至少一个数据   //分解之后进行合并
        while (s1 <= mid && s2 <= end) {
            if (array[s1] <= array[s2]) {
                tmp[k++] = array[s1++];//先赋值，再++。
            }else {
                tmp[k++] = array[s2++];
            }
            //两个数组中的数据可能是不一样多的，所以在一对一比较的时候可能会剩下数据
            //当s1或s2剩下数据的时候，就把剩下的数据合并到新的数组中即可。
        }

        while (s1 <= mid) {  //说明s1中还有数据
            tmp[k++] = array[s1++];
        }
        while (s2 <= end) {//说明s2中还有数据
            tmp[k++] = array[s2++];
        }
        //合并好之后的新数组中的元素要拷贝到原来的数组中去
        for (int i = 0; i < tmp.length; i++) {
            /*但是这样写有问题，如果是拷贝左边的数组就是从0下标开始去靠别就可以了
             * 但是拷贝右边的数组的时候，并不是0下标拷贝到0下标，右边的分解之后的数组
             * 的下标不是从0开始的*/
            //array[i] = tmp[i];
            array[i+start] = tmp[i];
        }
    }
    //非递归实现归并排序
    //思路：先看成是一个一个是有序的，再让两个两个有序，然后再进行合并
    public static void mergrSort3(int[] array) {
        int gap = 1;//每一个数据就是一组，相当于每个数据对于这组来说都是有序的
        while (gap < array.length) {//分的组不能超过数组的长度
            for (int i = 0; i < array.length; i += gap*2) {//因为是两组两组分的，这两组合并完成之后就进行下一次分组的合并
               int left = i;
               int mid = left+gap-1;//可能会越界
                if (mid >= array.length) {
                    mid = array.length-1;
                }
               int right = mid + gap;//可能会越界
                if (right >= array.length) {
                    right = array.length-1;
                }
               merge(array,left,right,mid);
            }
            gap *= 2;
        }

    }
    //计数排序
    /*    时间复杂度：
    *     空间复杂度：
    *     稳定性：*/
    public static void countSort(int[] array) {
        //1.先遍历整个数组拿到max值和min值   O（N）
        int max = array[0];
        int min = array[0];
        for (int i = 0; i < array.length; i++) {
            if (array[i] < min) {
                min = array[i];
            }
            if (array[i] > max) {
                max = array[i];
            }
        }
        //2.根据这组集中数据的max值和min值确定数组的长度
        int len = max - min + 1;
        int[] count = new int[len];
        //3.遍历数组，在计数器数组中记录每个数字出现的次数  O（N）
        for (int i = 0; i < array.length; i++) {
            count[array[i]-min]++;//必须-min，因为如果是0-9范围的数据就是0-9的下标
            //但是如果是90-99范围的数据，0下标计数的就是90  一次，所以要-min值
        }
        //4.遍历计数数组   O（取决于数组长度--数据的范围）
        int index = 0;
        for (int i = 0; i < count.length; i++) {
            while (count[i] > 0) {
                //放入的时候-min值了，放回来的时候这个数据还是原来的数据，
                // 反应真实的数据，要把最小值+回来
                array[index] = i+min;
                index++;
                count[i]--;
            }
        }
    }
}
